package java学习.算法.二叉树;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * **************
 * 项目名称: 蓝桥杯 <br/>
 * 文件名称:  <br/>
 * 文件描述: 这里添加您的类文件描述，说明当前文件要包含的功能。 <br/>
 * 文件创建：刘世锦 <br/>
 * 创建时间: 2022/3/20 <br/>
 *
 * @version v1.0 <br/>
 * @update [序号][日期YYYY-MM-DD][更改人姓名][变更描述]<br/>
 * *************
 */
public class BinTree {
    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }
    // 左、右要求一样，Info 表示信息返回的结构体
    public static class Info {
        // 是否平衡
        public boolean isBlanced;
        // 高度多少
        public int height;

        public Info(boolean b, int h) {
            isBlanced = b;
            height = h;
        }
    }
     boolean getIsBlance(Node node){
        return isBlanceTree(node).isBlanced;
     }

    /**
     *  是否是平衡二叉树
     * @param node
     * @return
     */
    public  static  Info isBlanceTree(Node node){
        int max = -1;
        Boolean blance = false;
        if (node==null){
            return new Info(true,0);
        }
        Info left = isBlanceTree(node.left);
        Info right = isBlanceTree(node.right);
        max = Math.max(left.height,right.height); // 树的高度等于左右最大高度，加上当前头结点的高度1
        if (left.isBlanced
                && right.isBlanced
                && Math.abs(left.height-right.height)<2){
                blance = true;
        }
        return new Info(blance,max+1);

    }

     static class DistanceInfo{
        int MaxDistance;
        int height;

         public DistanceInfo(int distance, int height) {
             MaxDistance = distance;
             this.height = height;
         }
     }

    /**
     * 返回二叉树任意两个节点最大值
     * @param head
     * @return
     */
     public static DistanceInfo MaxDis(Node head){
         int height = 0;
         int MaxDistance = 0;
        if (head==null){
            return new DistanceInfo(0,0);
        }
        DistanceInfo leftInfo = MaxDis(head.left);
        DistanceInfo rightInfo = MaxDis(head.right);

        // 当前树的高度：左右子树的最大高度+1.
        height = Math.max(leftInfo.height,rightInfo.height)+1;

        MaxDistance = Math.max(leftInfo.MaxDistance,rightInfo.MaxDistance);
        MaxDistance = Math.max(MaxDistance,leftInfo.height+rightInfo.height+1);
//         最大距离：
//         即:比较 max{过X时，左右子树高度+1,不过X时、左右子树的最距离}

        return new DistanceInfo( MaxDistance,height);
     }


    static class SearchInfo{
        boolean IsSearch; // 是否是搜索树
        int SearchSize;  //二叉搜索树的个数
        int max;
        int min;

        public SearchInfo(boolean isSearch, int searchSize, int max, int min) {
            IsSearch = isSearch;
            SearchSize = searchSize;
            this.max = max;
            this.min = min;
        }
    }

    /**
     * 找最大二叉搜索树
     * @param head
     * @return
     */
    public static SearchInfo MaxSearch(Node head){
        int SearchSize = 0;  //二叉搜索树的个数
        int max= head.value;
        int min= head.value;
        if (head==null){
            return null;
        }
        SearchInfo left =  MaxSearch(head.left);
        SearchInfo right =  MaxSearch(head.right);
        // 得到最大值、最小值
        /**
         * 尽管 最大值不一定就在左子树上，简言之；就是获取了全树的最大值和最小值
         *  min<X<max  则    left.max <X < right.min
         */
        if (left!=null){
            max = Math.max(max,left.max);
            min = Math.min(min,left.min);
        }
        if (right!=null){
            max = Math.max(max,right.max);
            min = Math.min(min,right.min);

        }
        // 不经过X
        if (left!=null){
            SearchSize = left.SearchSize;
        }
        if (right!=null){
            SearchSize = Math.max(SearchSize,right.SearchSize);
        }
        boolean IsSearch = false; // 是否是搜索树
        // 经过X：及时判空
//        if ( left.IsSearch
//                && right.IsSearch
//                && head.value>left.max
//                && head.value< right.min ){
//            IsSearch = true;
//            SearchSize = left.SearchSize + right.SearchSize + 1;
//        }
        if(
            // 左树和人右树整体需要是搜索二叉树
                (  left == null ? true : left.IsSearch    )
                &&
                (  right == null ? true : right.IsSearch    )
                &&
                // 左树最大值<X，右树最小值>X
                (left == null ? true : left.max < head.value)
                &&
                (right == null ? true : right.min > head.value)) {
             SearchSize =
                (left == null ? 0 : left.SearchSize) +
                (right == null ? 0 : right.SearchSize) + 1;
            IsSearch = true;


        }

        return new SearchInfo(IsSearch,SearchSize,max,min);
    }

    static class CBinaryInfo {
        boolean IsCBT; // 是否是CBT: 完全二叉树
        boolean IsFULL;
        int height;

        public CBinaryInfo(boolean isCBT, boolean isFULL,  int height) {
            IsCBT = isCBT;
            IsFULL = isFULL;
            this.height = height;
        }
    }

    /**
     * 是否是完全二叉树
     * @param head
     * @return
     */
    public static CBinaryInfo CBinaryTree(Node head){

        if (head==null){
            return new CBinaryInfo(true,true,0);
        }
        CBinaryInfo leftInfo = CBinaryTree(head.left);
        CBinaryInfo rightInfo = CBinaryTree(head.right);

        boolean IsCBT = false; // 是否是CBT: 完全二叉树

        int height = 0;
        // 最大高度
        height = Math.max(height,rightInfo.height)+1;
        // 是否是满二叉
        boolean IsFULL = leftInfo.IsFULL
                && rightInfo.IsFULL
                && leftInfo.height == rightInfo.height;
        // 无缺口： 都是满二叉树且高度相等。
        if (IsFULL){
            IsCBT = true;  // 如果是满二叉，则一定是完全二叉
        }else {              /* 左右都是完全二叉树才有讨论的必要 */
            if (leftInfo.IsCBT&&rightInfo.IsCBT){
                // 有缺口：
                // 1- 左子树完全，右子树满，Lh - Rh = 1;
                // 2-  左子树满，右子树满，Lh - Rh = 1;
                // 3-   左子树满，右子树完全，Lh =  Rh ;
                if (leftInfo.IsCBT
                        && rightInfo.IsFULL
                        && leftInfo.height-rightInfo.height ==1){
                    IsCBT = true;
                }
                if (leftInfo.IsFULL
                        && rightInfo.IsFULL
                        && leftInfo.height-rightInfo.height ==1){
                    IsCBT = true;
                }
                if (leftInfo.IsFULL
                        && rightInfo.IsCBT
                        && leftInfo.height-rightInfo.height ==0){
                    IsCBT = true;
                }
            }
        }


        return new CBinaryInfo(IsCBT,IsFULL,height);
        }

//    最低公共祖先
    public static Node lowestAncestor1(Node head, Node o1, Node o2) {
        if (head == null) {
            return null;
        }
        HashMap<Node, Node> map = new HashMap<>();
        map.put(head,null);
        getParentMap(head,map); // 将head、head的父放入map
        Set<Node> o1Set = new HashSet<>();
        // 将 o1 的父亲放入set
        o1Set.add(o1);
        Node parent = map.get(o1);
        while (parent!=null){
             parent = map.get(parent);
            o1Set.add(parent);
        }
        // 开始判断：
        while (!o1Set.contains(o2)){
            // 不包含 就 向上遍历o2的父节点的父：
            o2 = map.get(o2);
        }
        return o2;
    }

    public static void getParentMap(Node head,HashMap<Node, Node> map){
        if (head.left!=null){
            map.put(head.left,head);
            getParentMap(head.left,map);
        }
        if (head.right!=null){
            map.put(head.right,head);
            getParentMap(head.right,map);
        }
    }
}


